#include <iostream>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int minSubArrayLenViolence(int target, vector<int> &nums)
    {
        int sum;
        for (int sublen = 1; sublen <= nums.size(); sublen++)
        {
            for (int index = 0; index <= nums.size() - sublen; index++)
            {
                sum = 0;
                for (int i = 0; i < sublen; i++)
                {
                    sum += nums[index + i];
                }
                if (sum >= target)
                    return sublen;
            }
        }
        return 0;
    }

    int minSubArrayLenSelf(int target, vector<int> &nums)
    {
        int sum = 0, begin = 0, end = 0, minlen, result = INT_MAX;
        while (end < nums.size())
        {
            sum += nums[end];
            if (sum >= target)
            {
                minlen = end - begin + 1;
                result = min(minlen, result);
                end = ++begin;
                sum = 0;
                continue;
            }
            end++;
        }
        return result == INT_MAX ? 0 : result;
    }

    int minSubArrayLen(int s, vector<int>& nums) {
        if (nums.size()==0) {
            return 0;
        }
        int result = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while (end < nums.size()) {
            sum += nums[end];
            while (sum >= s) //对比上面自己的解法，while作为一个循环也能完成判断
            //先找到一个子串满足要求，可能存在更短的满足要求的的子串，更短子串的一定出现在更长子串的后侧，所以从头开始减起
            {
                result = min(result, end - start + 1);
                sum -= nums[start];
                //一一减掉开头的元素，
                //对比上面自己的解法，不需要重新加，更省时间
                start++;
            }
            //逐个减去开头直到不满足target，然后再向后添加元素
            end++;
        }
        return result == INT_MAX ? 0 : result;//一行解决if else判断
    }
    
};

int main()
{
    int n, target;
    cout << "size:";
    cin >> n;
    cout << "target:";
    cin >> target;
    vector<int> v1(n);
    for (int i = 0; i < n; i++)
    {
        cout << "input number " << i + 1 << ":";
        cin >> v1[i];
    }

    Solution s;
    cout << s.minSubArrayLen(target, v1);
}